package 力扣_树算法.搜索树;


/**450. 删除二叉搜索树中的节点
 * @author zx
 * @create 2022-04-16 12:48
 */
public class Num450 {
    /**
     * @return 自己整改的代码(简洁,适合面试)
     */
    public TreeNode deleteNode2(TreeNode root, int key) {
        if(root == null) return null;
        if(root.val > key) {
            root.left = deleteNode2(root.left, key);
        }else if(root.val < key) {
            root.right = deleteNode2(root.right, key);
        }else {//找到待删除节点,删除操作
            if(root.left == null){//待删除节点左子树为空
                TreeNode rightRoot = root.right;
                root.right = null;
                return rightRoot;
            }
            if(root.right == null){//待删除节点右子树为空
                TreeNode leftRoot = root.left;
                root.left = null;
                return leftRoot;
            }
            //以上两种情况也间接包括左右子树都为空的情况
            //待删除节点左右子树都不为空的情况
            //从当前节点的右子树中选择值最小的节点替代root,确保替代后仍满足BST特性
            TreeNode successor = min(root.right);
            successor.right = deleteMin(root.right);
            successor.left = root.left;
            //将要删除的节点和BST断开关系
            root.left = root.right = root = null;
            return successor;
        }
        return root;
    }
    /**
     * @return 返回以root为根的二分搜索树的最小值所在的节点(后继节点)
     */
    private TreeNode min2(TreeNode root) {
        if(root.left == null){
            return root;
        }
        return min2(root.left);
    }
    /**
     * 删除掉以node为根的二分搜索树的最小节点
     * @return 返回删除节点后新的二分搜索树的根
     */
    private TreeNode deleteMin2(TreeNode root) {
        if(root.left == null){
            return root.right;
        }
        root.left = deleteMin2(root.left);
        return root;
    }

    /**
     * @return bit代码：对后继节点的细节处理的很到位,适合理解性学习;但写起来代码难度大
     */
    public TreeNode deleteNode(TreeNode root, int key) {
        //1.左右子树都为空的情况
        //2.左子树为空的情况
        //3.右子树为空的情况
        if(root == null){
            return null;//二叉树不包含值为key的节点
        }
        if(root.val < key){
            root.right = deleteNode(root.right,key);
            return root;
        }else if(root.val > key){
            root.left = deleteNode(root.left,key);
            return root;
        }else{//找到待删除节点,删除操作
            if(root.left == null){//待删除节点左子树为空
                TreeNode rightRoot = root.right;
                root.right = null;
                return rightRoot;
            }
            if(root.right == null){//待删除节点右子树为空
                TreeNode leftRoot = root.left;
                root.left = null;
                return leftRoot;
            }
        //以上两种情况也间接包括左右子树都为空的情况
        //待删除节点左右子树都不为空的情况
        TreeNode successor = min(root.right);
        successor.right = deleteMin(root.right);
        successor.left = root.left;
        //将要删除的节点和BST断开关系
        root.left = root.right = root = null;
        return successor;
        }
    }
    /**
     * @return 返回以root为根的二分搜索树的最小值所在的节点(后继节点)
     */
    private TreeNode min(TreeNode node) {
        if(node.left == null){
            return node;
        }
        return min(node.left);
    }
    /**
     * 删除掉以node为根的二分搜索树的最小节点
     * @return 返回删除节点后新的二分搜索树的根
     */
    private TreeNode deleteMin( TreeNode node) {
        //递归出口
        if(node.left == null){
            //当前root就是待删除的节点
            TreeNode rightNode = node.right;//新建节点保存右子树
            node.right = null;
            return rightNode;
        }
        //递归去左子树中删除
        node.left = deleteMin(node.left);
        //node.left = **的作用就是将断了的节点重新连接起来
        return node;
    }
}
